/*
 * =====================================================================================
 *
 *       Filename:  pushpopsequence.c
 *
 *    Description:  generate or judge the push pop sequence
 *
 *        Version:  1.0
 *        Created:  2012年03月29日 10时53分56秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	"utility.h"
#include	<assert.h>
#define	    MAX_COUNT 10			/*  */

int judgeSequence(int *pushseq, int *popseq, int n)
{
    int *stack = malloc(sizeof(int) * (n+1));
    assert(stack != NULL);
    int i = 0, k = 0;
    int top = 0;
    for (i = 0; i < n; ++i)
    {
        if (pushseq[i] == popseq[k]) {
            ++k;
        } else {
            stack[top++] = pushseq[i];
        }
    }
    if (k < n)
    {
        assert(top == n - k);
        while (top)
        {
            if (stack[--top] != popseq[k++])
                return 0;
        }
        assert(n == k);
    }
    free(stack);
    return 1;
}

void myswap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

static int rightseq[MAX_COUNT+1];
static int seqptr = 0;

static int top_s = 0;
static int stack_s[MAX_COUNT+1];

void genRightSeq(int *x, int idx, int n)
{
    if (idx == n)
    {

        printf ( ">>>>>>>>>>seqptr:%d, top_s:%d\n", seqptr, top_s);
        //shouldn't change seqptr and top_s here
        int top = top_s;
        int off = seqptr;
        while (top > 0)
        {
            --top;
            rightseq[off] = stack_s[top];
            ++off;
        }
        printIntarr(rightseq, n);
        assert(judgeSequence(x, rightseq, n) == 1);
        printf ( "<<<<<<<<<<<<<<<<<<<<<\n" );
        return;
    }
//        int m1 = abs(rand()) % n;
//        int m2 = abs(rand()) % n;
//        if (m1 == m2) {
//            if (m1 == 0)
//                m2 = n-1;
//            else 
//                m2 = 0;
//        }
//        if (rightseq[m1] != rightseq[m2])
//        {
//            myswap(&rightseq[m1], &rightseq[m2]);
//            assert(judgeSequence(x, rightseq, n) == 0);
//            myswap(&rightseq[m1], &rightseq[m2]);
//        }

    rightseq[seqptr] = x[idx];
    ++seqptr;
    genRightSeq(x, idx+1, n);
    --seqptr;

    stack_s[top_s] = x[idx];
    ++top_s;
    genRightSeq(x, idx+1, n);
    --top_s;

    return;
}

int test()
{
    int times = 100;
    int seq[MAX_COUNT+1];
    while (times--)
    {
        top_s = 0;
        seqptr = 0;
        int n  = abs(rand()) % MAX_COUNT + 1;
        genRandInt(seq, n);
        printf ( "the original num sequence:\n" );
        printIntarr(seq, n);

        genRightSeq(seq, 0, n);
    }
    return 0;
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}
